快要考CSP了，还不会主席树？赶紧学习一下这个充满魅力的数据结构吧
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
主席树的使用范围
主席树被用于求解无增删可持续化区间操作的维护以及动态区间第k小值上。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
主席树的思想
当我们对一个数据结构进行可持续化时，如果对所有历史版本进行保存空间，复杂度会很高。因此我们可以使用可持续化线段树维护线性或树形数据结构，可持续化线段树又称主席树。
学***树的思想前，请学习前缀和思想、共用点、离散化、权值线段树、动态开点等知识。
以区间第k小值这个问题为例。
权值线段树可以对单个区间进行值域统计，其原理是先对数据进行离散化，再维护每个数出现的次数。如图（*图好难用啊啊啊）：
注意到权值线段树仅能维护一个区间。
考虑进行可持续化，如果我们对于从111到nnn的每个数i建一个维护区间111 ~ iii的权值线段树，当我们需要查询lll ~ rrr的第k小数时，对于每个节点，将其在rrr的版本的值减去其在l−1l-1l−1版本的大值，通过对差分的简单思考可知其正确性。
但是如果对于每一个元素都建一颗大小为4m4m4m（mmm为去重离散化后数组大小）的权值线段树，空间复杂度为O(4nm)O(4nm)O(4nm)，轻而易举MLE（跑完几十个数据点空间超崩铁了）
接下来（划重点）是主席树的核心思想：
----------------------动态开点-----------------------
怎么可能
并不是动态开点。但是记住动态开点是开一个结构体（空间更多了啊喂）存储线段树左端点和右端点在大胃袋数组中的编号以便查找（++cnt)，代码中将以实参函数的方式实现，《算法竞赛》中有返回值函数示例，欢迎诸位比我更蒟蒻的OIer参考。
主席树的核心思想是：存储链条。
种植一棵线段树，观察其生长过程，注意到权值线段树一开始是全是0的成都树空树，每次modify操作后，其结构有且仅有一条从叶子节点到根节点的链上的值发生改变。考虑对于每次操作存储链。
每次查询依旧用差分思想进行。
代码：
以下是本题代码：
建新树（当时使用了返回值，后来发现不如实参香，将就着看吧）：
查询：
离散化+初始化：
查询（细节\n加速）：
所有代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
我们需要更多主席树
依旧更多主席树：
P3919 【模板】可持久化线段树 1（可持久化数组）
P4137 Rmq Problem / mex
因为过于蒟蒻所以只会这几题+注意到主席树常数很大，空间复杂度也能把ST表击败，只能跑≤2×105\le 2\times 10 ^ 5≤2×105的数据，加上结合其它知识点难度较大，还是高贵的可持续化，所以洛谷题不多
本来此优秀算法可以跑教主，但是教主的NNN太大了，主席树需要O(Nlog2N)O(Nlog_2 N)O(Nlog2 N)建树，常数大跑不了，分块复杂度是O(MNlog2N)O(M{\sqrt N}log_2{\sqrt N})O(MN log2 N )，主要为mmm的大小主导，*壁的教主开了个很小的mmm，加上这mmm个查询肯定没跑满构造，所以现在唯一解是分块。
题解
可持续化数组这题，只需**叶子节点的值，运用普通线段树技巧可以完成。注意用i遍历MMM能很方便地进行时间增加操作，加上数组为初始即得，所以添加一个建全树的函数build,update用于开链树（好像只有我一个人这么叫它）
CodeCodeCode（快读快写+实参版本）:
NextNextNext
此题原用莫队，疯改回滚而灵机一动，提交题解发现题解亦不可过，故Hjted之（指主席树发明人黄嘉泰）
需要进行一定的思考，考虑修改当前权值对应的“最后一次出现的位置”为当前位置（参考题解原话），答案就是第rrr棵线段树上，第一个“最后一次出现的位置”小于lll的权值。（不是抄袭，原题解的表达比较适合描述算法就拿来用了，原作者）
CodeCodeCode:
重要的结尾
这么精心的文章不给个赞吗，诅咒所有不收藏的人CSP-S考到主席树（
